In multiprocessor computer systems, software programs may be executed by threads that are run in parallel on the processors that form the multiprocessor computer system. As a result, a program may be run in parallel on different processors since concurrently running threads may be executing the program simultaneously. Moreover, if a program can be broken down into constituent processes, such computer systems can run the program very quickly since concurrently running threads may execute in parallel the constituent processes. Single processor, multitasking computer systems can also execute multiple threads of execution virtually simultaneously through the use of various resource scheduling mechanisms well known to those skilled in the art of multitasking operating system design.
The programs run on such computer systems are often object oriented. In other words, the threads executing the programs may invoke methods of objects to perform particular functions. However, some methods of some objects may be implemented only one at a time because of hardware or software constraints in the computer system. For example, an object may require access to a shared computer resource, such as an I/O device, that can only handle one access by one thread at a time. Thus, since concurrently running threads may concurrently seek to invoke such an object, the object must be synchronized with only one thread at a time so that only that thread has exclusive use to the object (i.e., only one thread at a time can own a lock on the object).
In the past, various approaches have been used to synchronize an object with a thread. These include the use of synchronization constructs like mutexes, condition variables, and monitors. When using monitors, each monitor identifies the thread that currently owns the object and any threads that are waiting to own the object. However, in the computer systems that employ these monitors there is often a monitor for every synchronizable object. As a result, this approach has the distinct disadvantage of requiring a large amount of memory.
A simple approach to reducing the memory required by these monitors is to allocate a cache of monitors and to perform a hash table lookup on each monitor operation. Such an approach can substantially increase the overhead of monitor operations, and the slow speed of this solution led to the present invention. Moreover, the use of a single-shared hash table in and of itself requires some synchronization among the threads. Contention for this shared resource can result in additional computational overhead.
Another approach to object locking requires only one bit per object. The bit is used as a "semaphore" having two states, "locked" and "unlocked." Two operations are provided on these semaphores: one waits until the bit is in the "unlocked" state and then sets it to the "locked" state, all as one atomic operation; the other resets the bit to the "unlocked" state. This simple approach is of limited use in a processing environment where within a single thread of execution, a procedure makes repeated requests to lock an object that is already synchronized with the thread. Often, it is desirable to write software in a modular fashion where in a single thread of execution many procedures may call one another. For reasons of software reliability and ease of verification, it is also desirable for each procedure to be coded in such a way that it locks any object it needs. Frequently one procedure calls another, and each requires the same particular object to be locked. If each procedure attempts to lock the same object using the simple semaphore procedure, the second attempt will fail because the object is already locked. For this reason, a desirable property of an object locking system is that an object may be locked more than once by the same thread, while other threads are prevented from locking the object until the object is completely unlocked.
It is also a desirable property of an object locking system that frequently occurring operations require few accesses to main memory.
It is an object of the present invention to provide an object locking system in which only one bit per object of memory overhead is imposed, as for the simple semaphore approach, while allowing any one thread to lock the same object more than once. In such a system an object is considered to be unlocked only if the thread has performed as many unlock operations on the object as it has performed lock operations.
It is another object of the present invention to provide a locking system that requires no data structures to be shared among threads for locking purposes other than the one bit per object already mentioned.
It is another object of the present invention to provide an object locking system and method that is computationally efficient in requiring no access to main memory, other than to the one bit of the object, when a requesting thread does not currently hold a lock on any objects and the object for which a lock is being requested is currently unlocked.
It is another object of the present invention to provide an object locking system and method that is computationally efficient in requiring no access to main memory at all when a requesting thread has already locked one or more objects and the object to be locked by the requesting thread is the one that was most recently locked by the requesting thread.
Other general and specific objects of this invention will be apparent and evident from the accompanying drawings and the following description.